//给出一个无重叠的 ，按照区间起始端点排序的区间列表。 
//
// 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。 
//
// 
//
// 示例 1： 
//
// 输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
//输出：[[1,5],[6,9]]
// 
//
// 示例 2： 
//
// 输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
//输出：[[1,2],[3,10],[12,16]]
//解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
// 
//
// 
//
// 注意：输入类型已在 2019 年 4 月 15 日更改。请重置为默认代码定义以获取新的方法签名。 
// Related Topics 排序 数组 
// 👍 181 👎 0

package leetcode.editor.cn;

//Java：插入区间
public class P57InsertInterval {

    /**
     *
     * 思路：没插入之前是排好序的，所以只要在合适的地方插入newInterval，这道题就变成了 56题 排完序后的合并区间，之后把56题的代码复制过来就行了
     *
     * 执行用时： 2 ms , 在所有 Java 提交中击败了 77.01% 的用户 内存消耗： 42.3 MB , 在所有 Java 提交中击败了 13.81% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] insert(int[][] intervals, int[] newInterval) {
            int[][] newArr = new int[intervals.length + 1][2];
            int index;

            // 在已经排好序的 合适的地方插入 newInterval
            boolean flag = false;
            for (index = 0; index < intervals.length; index++) {
                if (newInterval[0] <= intervals[index][0] && !flag) {
                    flag = true;
                    newArr[index] = newInterval;
                }
                if (flag) {
                    newArr[index + 1] = intervals[index];
                } else {
                    newArr[index] = intervals[index];
                }
            }
            if (!flag) {
                newArr[intervals.length] = newInterval;
            }

            // 以下合并区间将56题的代码复制过来即可
            int now = 0;
            for (int j = 1; j < newArr.length; j++) {
                // 头个相同
                if (newArr[j][0] == newArr[now][0]) {
                    newArr[now][0] = newArr[j][0];
                    if (newArr[j][1] >= newArr[now][1]) {
                        newArr[now][1] = newArr[j][1];
                    }
                } else {
                    if (newArr[now][1] >= newArr[j][0]) {
                        newArr[now][1] = newArr[now][1] > newArr[j][1] ? newArr[now][1] : newArr[j][1];
                    } else {
                        now++;
                        newArr[now] = newArr[j];
                    }
                }
            }

            int[][] result = new int[now + 1][2];
            for (int i = 0; i <= now; i++) {
                result[i] = newArr[i];
            }
            return result;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        int[][] nums = new int[][]{{1,2},{3,5},{6,7},{8,10},{12,16}};
        int[] b = new int[]{4, 8};
        Solution solution = new P57InsertInterval().new Solution();
        int[][] a = solution.insert(nums, b);
        System.out.println(a);
        // TO TEST
    }

}